package com.mc.sort;

import com.mc.general.Tools;

public class MergeSort {
	private static Comparable[] temp;
	private static int[] sup;
	public static <T extends Comparable<T>> void sort(T[] array){
		int n = array.length;
		temp = new Comparable[n];
		sort(array,0,n-1);
	}
	private static <T extends Comparable<T>> void sort(T[] array,int low, int high){
		if(high<=low)return;
		int mid = low+(high-low)/2;
		sort(array,low,mid);
		sort(array,mid+1,high);
		merge(array,low,mid,high);
	}
	private static <T extends Comparable<T>> void merge(T[] array, int low,int mid, int high){
		int i = low ;
		int j = mid+1;
		for(int k=low;k<=high;k++){
			temp[k] = array[k];
		}
		for(int k = low;k<=high;k++){
			if(i>mid) array[k] = (T)temp[j++];
			else if (j>high) array[k] = (T)temp[i++];
			else if (Tools.compare((T)temp[i], (T)temp[j])==-1) array[k]=(T)temp[i++];
			else array[k]=(T)temp[j++];
		}
	}
	
	public static void sortInt(int[] a){
		sup = new int[a.length];
		sortInt(a,0,a.length-1);
	}
	public static void sortInt(int[] a,int low ,int high){
		if(high<=low)return;
		int mid = low+(high-low)/2;
		sortInt(a, low, mid);
		sortInt(a,mid+1,high);
		merge(a,low,mid,high);
	}
	private static void merge(int[] a, int low,int mid, int high){
		int i = low;
		int j = mid+1;
		for(int k=low;k<=high;k++){
			sup[k] = a[k];
		}
		for(int k=low;k<=high;k++){
			if(i>mid)a[k]=sup[j++];
			else if(j>high)a[k]=sup[i++];
			else if(sup[i]<sup[j])a[k]=sup[i++];
			else a[k]=sup[j++];
		}
	}
	public static void main(String[] args) {
		int[] a = new int[]{3,45,12,5,3,6};
		MergeSort.sortInt(a);
		for(int i:a)
			System.out.println(i);
	}
}
